In
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrices.
...
, the Crout matrix decomposition is an
LU decomposition
In numerical analysis and linear algebra, lower–upper (LU) decomposition or factorization factors a matrix as the product of a lower triangular matrix and an upper triangular matrix (see matrix decomposition). The product sometimes includes a pe ...
which decomposes a
matrix
Matrix most commonly refers to:
* ''The Matrix'' (franchise), an American media franchise
** ''The Matrix'', a 1999 science-fiction action film
** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
into a
lower triangular matrix
In mathematics, a triangular matrix is a special kind of square matrix. A square matrix is called if all the entries ''above'' the main diagonal are zero. Similarly, a square matrix is called if all the entries ''below'' the main diagonal are ...
(L), an
upper triangular matrix
In mathematics, a triangular matrix is a special kind of square matrix. A square matrix is called if all the entries ''above'' the main diagonal are zero. Similarly, a square matrix is called if all the entries ''below'' the main diagonal are ...
(U) and, although not always needed, a
permutation matrix
In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column and 0s elsewhere. Each such matrix, say , represents a permutation of elements and, when ...
(P). It was developed by
Prescott Durand Crout
Prescott Durand Crout (July 28, 1907 – September 25, 1984) was an American mathematician.
Crout was born in Ohio, but lived and worked in Massachusetts. In 1929 he finished the MIT class. His PhD thesis (supervisor: George Rutledge) was enti ...
.
The Crout matrix decomposition
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
differs slightly from the
Doolittle method. Doolittle's method returns a unit lower triangular matrix and an upper triangular matrix, while the Crout method returns a lower triangular matrix and a unit upper triangular matrix.
So, if a matrix decomposition of a matrix A is such that:
:A = LDU
being L a unit lower triangular matrix, D a diagonal matrix and U a unit upper triangular matrix, then Doolittle's method produces
:A = L(DU)
and Crout's method produces
:A = (LD)U.
Implementations
C implementation:
void crout(double const **A, double **L, double **U, int n)
Octave/Matlab implementation:
function , U
The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline (t ...
= LUdecompCrout(A)
, C= size(A);
for i = 1:R
L(i, 1) = A(i, 1);
U(i, i) = 1;
end
for j = 2:R
U(1, j) = A(1, j) / L(1, 1);
end
for i = 2:R
for j = 2:i
L(i, j) = A(i, j) - L(i, 1:j - 1) * U(1:j - 1, j);
end
for j = i + 1:R
U(i, j) = (A(i, j) - L(i, 1:i - 1) * U(1:i - 1, j)) / L(i, i);
end
end
end
References
Implementation using functions In Matlab
{{DEFAULTSORT:Crout Matrix Decomposition
Matrix decompositions